﻿using System;
using System.Collections.Generic;
using System.Collections;
using System.Linq;
using System.Text;
using GraphBase.Interfaces;

namespace GraphBase.Core
{
    public class Operations
    {
        private struct DepthFirstStruct
        {
            public IVertex m_vertex;
            public IEnumerator m_edges;
            public DepthFirstStruct(IVertex vertex, IEnumerator edges)
            {
                m_vertex = vertex;
                m_edges = edges;
            }
        }

        /// <summary>
        /// Breadth first query
        /// All callbacks may be null.
        /// Method returns true if short circuited, false otherwise.
        /// <code>
        /// while (levels) {
        ///     Update()
        ///     foreach( vertex in vertexes ) {
        ///         callback(vertex)
        ///         foreach( edge in edges ) {
        ///             if ( pred( edge ) )
        ///                 return true;
        ///         }
        ///     }
        /// }
        /// </code>
        /// </summary>
        /// <param name="rootVertexes">List of roots to start search from.</param>
        /// <param name="update">Called before updating each level of breadth first search</param>
        /// <param name="callback">Called for each vertex before grabbing the required edges</param>
        /// <param name="shortCircuit">Predicate to short-circuit query.  Query stops if pred returns true</param>
        /// <param name="edgeFilter">Predicate to filter list of edges included in next level of processing</param>
        /// <param name="incoming">True to process the incoming edges.  False to process outgoing</param>
        /// <returns>True if short circuited, false otherwise</returns>
        public static bool RunBreadthFirstQuery(IEnumerable rootVertexes, QueryUpdate update, VertexCallback callback
            , Predicate<IEdge> shortCircuit, Predicate<IEdge> edgeFilter, bool incoming)
        {
            if (rootVertexes == null)
                throw new ArgumentNullException("rootVertexes");

            List<IVertex> listOne = new List<IVertex>();
            List<IVertex> listTwo = new List<IVertex>();

            List<IVertex> activeList = listOne;
            List<IVertex> nextList = listTwo;

            foreach (IVertex vert in rootVertexes)
                activeList.Add(vert);
            while (activeList.Count != 0)
            {
                if ( update != null )
                    update();
                foreach (IVertex vertex in activeList)
                {
                    if (callback != null)
                        callback(vertex);
                    foreach (IEdge edge in NextEdges(vertex, incoming))
                    {
                        if (edgeFilter == null || edgeFilter(edge))
                        {
                            if (shortCircuit != null && shortCircuit(edge))
                                return true;
                            nextList.Add(NextVertex(edge, incoming));
                        }
                    }
                }
                activeList.Clear();
                activeList = nextList;
                //Swap the lists.
                nextList = activeList == listOne ? listTwo : listOne;
            }
            return false;
        }

        /// <summary>
        /// Depth first query.
        /// Probably not done using recursion as these graphs
        /// could be quite large.
        /// All callbacks may be null.
        /// Method returns null when short circuited, false otherwise.
        /// <code>
        /// beginVertex(this)
        /// foreach( Edge edge in edges )
        /// {
        ///     if ( pred( edge ) || RunDepthFirstQuery( edge.vertex ) ) {
        ///         return true;
        ///     }
        /// }
        /// endVertex(this);
        /// return false;
        /// </code>
        /// </summary>
        /// <param name="rootVertex">Vertex to start search from; may be null</param>
        /// <param name="beginVertex">Callback before processing a vertex</param>
        /// <param name="endVertex">Callback before ending processing of a vertex</param>
        /// <param name="shortCicuit">Predicate to decide whether to continue query</param>
        /// <param name="edgeFilter">If not null, used to limit query without short circuit.</param>
        /// <param name="incoming">True if processing the incoming edges.  False to process outgoing</param>
        /// <returns>true if short circuited, false otherwise</returns>
        public static bool RunDepthFirstQuery(IVertex rootVertex, VertexCallback beginVertex, VertexCallback endVertex
            , Predicate<IEdge> shortCircuit, Predicate<IEdge> edgeFilter, bool incoming)
        {
            if (rootVertex == null)
                throw new ArgumentNullException("rootVertex");
            Stack<DepthFirstStruct> vertStack = new Stack<DepthFirstStruct>();
            vertStack.Push(new DepthFirstStruct(rootVertex, NextEdges(rootVertex, incoming).GetEnumerator()));
            while (vertStack.Count != 0)
            {
                if ( beginVertex != null )
                    beginVertex(vertStack.Peek().m_vertex);
                bool processed = false;
                while (vertStack.Peek().m_edges.MoveNext())
                {
                    IEdge nextEdge = (IEdge)vertStack.Peek().m_edges.Current;
                    if (edgeFilter == null || edgeFilter(nextEdge))
                    {
                        processed = true;
                        if (shortCircuit != null && shortCircuit(nextEdge))
                            return true;
                        IVertex nextVert = NextVertex(nextEdge, incoming);
                        vertStack.Push(new DepthFirstStruct(nextVert, NextEdges(nextVert, incoming).GetEnumerator()));
                        break;
                    }
                }
                if ( !processed )
                {
                    if ( endVertex != null )
                        endVertex(vertStack.Peek().m_vertex);
                    vertStack.Pop();
                }
            }
            return false;
        }

        public static ICollection NextEdges(IVertex vertex, bool incoming)
        {
            return incoming ? vertex.IncomingEdges : vertex.OutgoingEdges;
        }

        public static IVertex NextVertex(IEdge edge, bool incoming)
        {
            return incoming ? edge.IncomingVertex : edge.OutgoingVertex;
        }
    }
}
